package primary.primary2;

public class S2560打家劫舍IV {


    /**
     *
     */
    public int minCapability2(int[] nums, int k) {
        int left = 0, right = (int) 1e9;
        while (left + 1 < right) {
            int mid = (left + right) >>> 1;
            int f0 = 0, f1 = 0;
            for (int x : nums)
                if (x > mid) f0 = f1;
                else {
                    int tmp = f1;
                    f1 = Math.max(f1, f0 + 1);
                    f0 = tmp;
                }
            if (f1 >= k) right = mid;
            else left = mid;
        }
        return right;
    }


    /**
     * 不会写
     * 感觉因为有 相邻 这个概念，所以它依然是动态规划，不是什么其他类型的解法
     * 这题是返回被窃取的房屋里面的最大值，但是要找到让这个最大值最小的一组被窃取的房屋，挺绕的。
     * 如果是返回被偷的房屋val和的话，又是另一个题目了
     * 不是总体的倒数第k个，因为最小的那些可能会连着
     * 用动态规划，但是感觉要维护2个k长度的数组，复杂度变成 k * nums.length，有点长。
     * 有没有可能不窃取k是最大值?最少k个，可以多吗?多的话，会导致最大值可以更小吗?
     */
    public int minCapability(int[] nums, int k) {

        int[] preStealed = new int[k];
        int[] preUnStealed = new int[k];
        for(int i = 0; i < nums.length; i++){
            int[] curStealed = new int[k];
            int[] curUnStealed = new int[k];
            // 注意边界条件
            for(int j = 1; j < k; j++){
                curStealed[j] = preUnStealed[j - 1] + nums[i];
                curUnStealed[j] = Math.min(preStealed[j], preUnStealed[j]);
            }
            preStealed = curStealed;
            preUnStealed = curUnStealed;
        }
        return Math.min(preStealed[k - 1], preUnStealed[k - 1]);
    }
}
